package com.shm.leetcode;

/**
 * 91. 解码方法
 * 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
 *
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
 *
 * "AAJF" ，将消息分组为 (1 1 10 6)
 * "KJF" ，将消息分组为 (11 10 6)
 * 注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
 *
 * 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
 *
 * 题目数据保证答案肯定是一个 32 位 的整数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "12"
 * 输出：2
 * 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
 * 示例 2：
 *
 * 输入：s = "226"
 * 输出：3
 * 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
 * 示例 3：
 *
 * 输入：s = "0"
 * 输出：0
 * 解释：没有字符映射到以 0 开头的数字。
 * 含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
 * 由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
 * 示例 4：
 *
 * 输入：s = "06"
 * 输出：0
 * 解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 100
 * s 只包含数字，并且可能包含前导零。
 * @author SHM
 */
public class NumDecodings {
    /**
     * 基本分析
     * 我们称一个解码内容为一个 item。
     *
     * 为根据题意，每个 item 可以由一个数字组成，也可以由两个数字组成。
     *
     * 数据范围为 100，很具有迷惑性，可能会有不少同学会想使用 DFS 进行爆搜。
     *
     * 我们可以大致分析一下这样的做法是否可行：不失一般性的考虑字符串 s 中的任意位置 i，位置 i 既可以作为一个独立 item，也可以与上一位置组成新 item，那么相当于每个位置都有两种分割选择（先不考虑分割结果的合法性问题），这样做法的复杂度是 O(2^n)O(2
     * n
     *  ) 的，当 n 范围是 100 时，远超我们计算机单秒运算量（10^710
     * 7
     *  ）。即使我们将「判断分割结果是否合法」的操作放到爆搜过程中做剪枝，也与我们的单秒最大运算量相差很远。
     *
     * 递归的方法不可行，我们需要考虑递推的解法。
     *
     * 动态规划
     * 这其实是一道字符串类的动态规划题，不难发现对于字符串 s 的某个位置 i 而言，我们只关心「位置 i 自己能否形成独立 item 」和「位置 i 能够与上一位置（i-1）能否形成 item」，而不关心 i-1 之前的位置。
     *
     * 有了以上分析，我们可以从前往后处理字符串 s，使用一个数组记录以字符串 s 的每一位作为结尾的解码方案数。即定义 f[i]f[i] 为考虑前 ii 个字符的解码方案数。
     *
     * 对于字符串 s 的任意位置 i 而言，其存在三种情况：
     *
     * 只能由位置 i 的单独作为一个 item，设为 a，转移的前提是 a 的数值范围为 [1,9][1,9]，转移逻辑为 f[i] = f[i - 1]f[i]=f[i−1]。
     * 只能由位置 i 的与前一位置（i-1）共同作为一个 item，设为 b，转移的前提是 b 的数值范围为 [10,26][10,26]，转移逻辑为 f[i] = f[i - 2]f[i]=f[i−2]。
     * 位置 i 既能作为独立 item 也能与上一位置形成 item，转移逻辑为 f[i] = f[i - 1] + f[i - 2]f[i]=f[i−1]+f[i−2]。
     * 因此，我们有如下转移方程：
     *
     * \begin{cases} f[i] = f[i - 1], 1 \leqslant a \leq 9 \\ f[i] = f[i - 2], 10 \leqslant b \leqslant 26 \\ f[i] = f[i - 1] + f[i - 2], 1 \leqslant a \leq 9, 10 \leqslant b \leqslant 26 \\ \end{cases}
     * ⎩
     * ⎪
     * ⎪
     * ⎨
     * ⎪
     * ⎪
     * ⎧
     * ​
     *
     * f[i]=f[i−1],1⩽a≤9
     * f[i]=f[i−2],10⩽b⩽26
     * f[i]=f[i−1]+f[i−2],1⩽a≤9,10⩽b⩽26
     * ​
     *
     * 其他细节：由于题目存在前导零，而前导零属于无效 item。可以进行特判，但个人习惯往字符串头部追加空格作为哨兵，追加空格既可以避免讨论前导零，也能使下标从 1 开始，简化 f[i-1] 等负数下标的判断。
     *
     * 时间复杂度：共有 n 个状态需要被转移。复杂度为 O(n)O(n)。
     * 空间复杂度：O(n)O(n)。
     * 作者：AC_OIer
     * 链接：https://leetcode-cn.com/problems/decode-ways/solution/gong-shui-san-xie-gen-ju-shu-ju-fan-wei-ug3dd/
     * 方法一：动态规划
     * 思路与算法
     *
     * 对于给定的字符串 ss，设它的长度为 nn，其中的字符从左到右依次为 s[1], s[2], \cdots, s[n]s[1],s[2],⋯,s[n]。我们可以使用动态规划的方法计算出字符串 ss 的解码方法数。
     *
     * 具体地，设 f_if
     * i
     * ​
     *   表示字符串 ss 的前 ii 个字符 s[1..i]s[1..i] 的解码方法数。在进行状态转移时，我们可以考虑最后一次解码使用了 ss 中的哪些字符，那么会有下面的两种情况：
     *
     * 第一种情况是我们使用了一个字符，即 s[i]s[i] 进行解码，那么只要 s[i] \neq 0s[i]
     * 
     * ​
     *  =0，它就可以被解码成 \text{A} \sim \text{I}A∼I 中的某个字母。由于剩余的前 i-1i−1 个字符的解码方法数为 f_{i-1}f
     * i−1
     * ​
     *  ，因此我们可以写出状态转移方程：
     *
     * f_i = f_{i-1}, \quad 其中 ~ s[i] \neq 0
     * f
     * i
     * ​
     *  =f
     * i−1
     * ​
     *  ,其中 s[i]
     * 
     * ​
     *  =0
     *
     * 第二种情况是我们使用了两个字符，即 s[i-1]s[i−1] 和 s[i]s[i] 进行编码。与第一种情况类似，s[i-1]s[i−1] 不能等于 00，并且 s[i-1]s[i−1] 和 s[i]s[i] 组成的整数必须小于等于 2626，这样它们就可以被解码成 \text{J} \sim \text{Z}J∼Z 中的某个字母。由于剩余的前 i-2i−2 个字符的解码方法数为 f_{i-2}f
     * i−2
     * ​
     *  ，因此我们可以写出状态转移方程：
     *
     * f_i = f_{i-2}, \quad 其中 ~ s[i-1] \neq 0 ~并且~ 10\cdot s[i-1]+s[i] \leq 26
     * f
     * i
     * ​
     *  =f
     * i−2
     * ​
     *  ,其中 s[i−1]
     * 
     * ​
     *  =0 并且 10⋅s[i−1]+s[i]≤26
     *
     * 需要注意的是，只有当 i>1i>1 时才能进行转移，否则 s[i-1]s[i−1] 不存在。
     *
     * 将上面的两种状态转移方程在对应的条件满足时进行累加，即可得到 f_if
     * i
     * ​
     *   的值。在动态规划完成后，最终的答案即为 f_nf
     * n
     * ​
     *  。
     *
     * 细节
     *
     * 动态规划的边界条件为：
     *
     * f_0 = 1
     * f
     * 0
     * ​
     *  =1
     *
     * 即空字符串可以有 11 种解码方法，解码出一个空字符串。
     *
     * 同时，由于在大部分语言中，字符串的下标是从 00 而不是 11 开始的，因此在代码的编写过程中，我们需要将所有字符串的下标减去 11，与使用的语言保持一致。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/decode-ways/solution/jie-ma-fang-fa-by-leetcode-solution-p8np/
     * @param s
     * @return
     */
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n+1];
        s=" "+s;
        //细节
        //动态规划的边界条件为：
        //f_0 = 1
        //即空字符串可以有 11 种解码方法，解码出一个空字符串。
        dp[0]=1;
        for(int i=1;i<=n;i++){
            // a : 代表「当前位置」单独形成 item
            // b : 代表「当前位置」与「前一位置」共同形成 item
            int a=s.charAt(i)-'0',b=(s.charAt(i-1)-'0')*10+(s.charAt(i)-'0');
            // 如果 a 属于有效值，那么 f[i] 可以由 f[i - 1] 转移过来
            if(1<=a&&a<=9){
                dp[i]=dp[i-1];
            }
            // 如果 b 属于有效值，那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
            if(10<=b&&b<=26){
                dp[i]+=dp[i-2];
            }
        }
        return dp[n];
    }

    /**
     * 空间优化
     * 不难发现，我们转移 f[i] 时只依赖 f[i-1] 和 f[i-2] 两个状态。
     *
     * 因此我们可以采用与「滚动数组」类似的思路，只创建长度为 3 的数组，通过取余的方式来复用不再需要的下标。
     *
     * 时间复杂度：共有 n 个状态需要被转移。复杂度为 O(n)O(n)。
     * 空间复杂度：O(1)O(1)。
     * 作者：AC_OIer
     * 链接：https://leetcode-cn.com/problems/decode-ways/solution/gong-shui-san-xie-gen-ju-shu-ju-fan-wei-ug3dd/
     * @param s
     * @return
     */
    public int numDecodings_2(String s) {
        int n = s.length();
        s = " " + s;
        int[] dp = new int[3];
        dp[0]=1;
        for (int i = 1; i <= n; i++) {
            int a=s.charAt(i)-'0',b=(s.charAt(i-1)-'0')*10+(s.charAt(i)-'0');
            dp[i%3]=0;
            if(1<=a&&a<=9){
                dp[i%3]=dp[(i-1)%3];
            }
            if(10<=b&&b<=26){
                dp[i%3]+=dp[(i-2)%3];
            }
        }
        return dp[n%3];
    }
}
